#include <bits/stdc++.h>
using namespace std;
class MyLinkedList {
  struct Node {
    int val;
    Node *prev, *next;
  };
  Node *head, *tail;
  int sz;
  Node* at(int index) {
    if (index >= sz) return 0;
    Node* cur = head->next;
    for (int i = 0; i < index; i ++) cur = cur->next;
    return cur;
  }
public:
  MyLinkedList() {
    head = new Node{0, 0, 0};
    tail = new Node{0, head, 0};
    head->next = tail;
    sz = 0;
  }
  
  int get(int index) {
    Node* cur = at(index);
    if (cur) return cur->val;
    return -1;
  }
  
  void addAtHead(int val) {
    Node* first = head->next;
    Node* new_node = new Node(val, head, first);
    first->prev = new_node;
    head->next = new_node;
    sz ++;
  }
  
  void addAtTail(int val) {
    Node* last = tail->prev;
    Node* new_node = new Node(val, last, tail);
    last->next = new_node;
    tail->prev = new_node;
    sz ++;
  }
  
  void addAtIndex(int index, int val) {
    if (index == sz) {
      addAtTail(val);
      return;
    }
    Node *cur = at(index);
    if (!cur) return;
    Node *prev = cur->prev;
    Node *new_node = new Node(val, prev, cur);
    prev->next = new_node;
    cur->prev = new_node;
    sz ++;
  }
  
  void deleteAtIndex(int index) {
    Node *cur = at(index);
    if (!cur) return;
    Node *prev = cur->prev, *next = cur->next;
    prev->next = next;
    next->prev = prev;
    delete cur;
    sz --;
  }
};
/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */